import java.util.Random;

public class Test {

    //分治-快排


    //最小的k个数
    public int[] getLeastNumbers(int[] nums, int k){
        qsort1(nums,0,nums.length-1,k);
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = nums[i];
        }
        return ret;
    }

    public void qsort1(int[] nums,int l,int r, int k){
        if (l == r) return;

        int key = nums[new Random().nextInt(r-l+1) +l];
        int left = l-1,right = r+1, i = l;
        while(i < right){
            if (nums[i] <key) swap(nums,++left,i++);
            else if(nums[i] == key) i++;
            else swap(nums,--right,i++);
        }

        int a = left - l +1,b = right-left-1;
        if (a>k) qsort(nums,l,left,k);
        else if(a+b>=k) return;
        else qsort(nums,right,r,k-a-b);
    }


    //快速选择算法
    //数组中的第k个最大元素
    public  int findKthLargest(int[] nums,int k){
        return qsort(nums,0,nums.length-1,k);
    }

    public int qsort(int[] nums,int l,int r,int k){
        if (l == r) return nums[l];

        int key = nums[new Random().nextInt(r-l+1)+l];
        int left = l-1,right = r+1,i = l;
        while(i<right){
            if (nums[i] <key) swap(nums,++left,i++);
            else if(nums[i] == key) i++;
            else swap(nums,--right,i);
        }

        int c = r-right+1,b = right -left -1;
        if (c>=k) return qsort(nums,right,r,k);
        else if(c+b >= k) return key;
        else return qsort(nums,l,left,k-b-c);
    }


    //快速排序
    public int[] sortArray(int[] nums){
        qsort(nums,0,nums.length-1);
        return nums;
    }
    public void qsort(int[] nums, int l,int r){
        if (l>=r) return;

        int key = nums[new Random().nextInt(r-l+1)+l];
        int left = l-1,right = r+1,i = l;
        while (i<right){
            if (nums[i] < key) swap(nums,++left,i++);
            else if(nums[i] > key) swap(nums,--right,i);
            else i++;
        }

        qsort(nums,l,left);
        qsort(nums,right,r);
    }


    //颜色分类
    public void swap(int[] nums,int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public void sortColors(int[] nums){
        int left = -1,right = nums.length,i = 0;
        while(i<right){
            if (nums[i] == 0) swap(nums,++left,i++);
            else if(nums[i] == 1) swap(nums,--right,i);
            else i++;
        }
    }


}
